In modern computer systems, data is constantly written to and read front several memory devices. One such device is a disk drive. While disk drives are used for permanent or non-volatile data storage on a magnetic or optical disk, they typically use internal volatile memory such as SDRAM to stage data before writing data to the disk. The SDRAM is also used to stage data after reading it from the disk, before it is sent to the host. However, every staging operation in the SDRAM creates an opportunity for error, both from the host to the disk and from the disk to the host. As a result, some method of error detection (and sometimes correction) must be employed every time data is transferred, even within the disk drive.
In the disk drives just described, when the data is received from the host and written to the staging memory, error detection capability is typically added. A relatively simple, low overhead algorithm such as Cyclical Redundancy Check (CRC) can determine whether there are any errors in the data. As the data is written to the staging memory, the CRC algorithm adds some check bits to the data that allow for detection of errors when the data is read at a later time. At a desired time, the data is read from the staging memory and sent to the disk.
As the data is read from the staging memory, the CRC algorithm reads the data and the check bits to determine whether there are any errors in the data. If there are errors, the data is re-requested from the host and the process is repeated, until the data is transferred to the disk without errors. The CRC algorithm need not correct errors, however, because if there are errors, the data can be re-requested from the host until the data transfer is successfully completed without errors. Thus, it is not necessary for the CRC algorithm to identify or correct errors at this stage. The CRC algorithm merely determines whether any errors exist in the data.
The data is also checked for errors when it is sent through the staging memory in the other direction, i.e., from the disk to the host. Thus, when the data is received from the disk and the data is written to the staging memory, the CRC algorithm adds CRC check bits to the data. When the data is read from the staging memory, the CRC algorithm checks the data and CRC bits to determine whether there are errors. In the case of an error, the data is re-requested from the disk and the operation repeats until the data is successfully transferred without errors.
Insuring the integrity of the data stored on the disk requires a more complex error correction algorithm. If the data stored on the disk has errors, the errors must be identified and corrected without rereading the data, because the errors are likely stored on the disk and the data is presumably not available from the host or another source. In this case, a more sophisticated algorithm must be used that can identify the errors and correct them.
Error identification and correction requires more complex, relatively high overhead algorithms. Such algorithms produce data strings, commonly called Error Correction Codes (ECCs), that are stored on the disk with the data. When the data is read from the disk, it is checked against the ECC's, and if errors are detected, most of the errors can be identified and corrected. Some ECC implementations use a Cyclical Redundancy Check algorithm that verifies that the errors have been corrected, as desired.
Data is generally written to and read out of the disk in sectors containing some number of bytes, such as 512 bytes, or 4096 bits. As the first sector is read from the disk, it is immediately written to the staging memory. At the same time, the ECC algorithm is executed, and a CRC value is calculated. If an error is found by the ECC algorithm, mask data is generated that specifies which bytes in the SDRAM should be corrected. Then, the erroneous bytes are read from the SDRAM and XORed with the mask data and written back to the SDRAM. The CRC mask is calculated using the mask data from the ECC algorithm. In this manner, the data and CRC value can be corrected without re-reading the whole sector from the SDRAM.
In the past, a typical disk drive used a single bit length or symbol length for data and for its ECC algorithm. Recently, however, ECC algorithms using 10 bit symbols have been adopted, even though the host still communicates in 8 bit symbols, the staging memories store data based on 8 bit symbols, and the CRC algorithm is also based on those 8 bit symbols. This is a problem because the mask segments created by the ECC algorithm do not directly correspond to or lie over the data bytes, so the CRC value cannot merely be calculated according to the ECC mask layout to complete the correction process.
The CRC values could be recalculated by re-reading the whole corrected sector from the SDRAM, but that process would be time consuming, and would slow the operation of the drive. Thus, there is a need for methods and apparatus for correcting data and error detection codes on the fly, without reading the data after it has been corrected.
Another problem encountered when the ECC algorithm processes the data in symbols having a different size than the symbols in which the data is organized is that if the ECC bit symbols cannot divide evenly into the number of bits in the sectors, the remainder is difficult to process. If the sector has 4,096 bits, for example, an algorithm that uses 10 bit symbols for processing purposes will process 409 symbols, and have 6 bits remaining. The CRC calculation fails because it is based on 4090 bits or 4100 bits, not 4096 bits. Thus, there is a need for methods and apparatus for correcting the CRC calculations, irrespective of whether the symbol length of a correction algorithm is evenly divisible into the number of bits in a sector.
If a disk drive controller operates on the basis of a single sector size, the control can only be used for that sector size. This limits the flexibility of the controller. Thus, there is a need for methods and apparatus for detecting errors in data, regardless of the sector size.